package LeetCode;

import javax.swing.plaf.IconUIResource;
import java.awt.print.PrinterGraphics;
import java.util.ArrayList;
import java.util.List;

public class LeetCode1177 {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        List<Boolean> list = new ArrayList<>();
        for (int[] query : queries) {
            int[] arr = query;
            int left = arr[0];
            int right = arr[1];
            int k = arr[2];
            if (left == right){
                list.add(true);
                continue;
            }
            String index = s.substring(left,right + 1);
            char[] chars = index.toCharArray();
            boolean flag = isPlalindrome(chars);
            if (flag){
                list.add(true);
            }else {
                if (k == 0){
                    list.add(false);
                }else {
                    if (index.length() % 2 == 0){
                        int l = index.length() / 2 - 1;
                        int r = l + 1;
                        int count = 0;
                        while (l >= 0 && r < index.length()){
                            if (chars[l] != chars[r]){
                                count++;
                            }
                            l--;
                            r++;
                        }
                        if (count > k){
                            list.add(false);
                        }else {
                            list.add(true);
                        }
                    }else {
                        int l = index.length() / 2;
                        int r = l;
                        int count = 0;
                        while (l >= 0 && r < index.length()){
                            if (chars[l] != chars[r]){
                                count++;
                            }
                            l--;
                            r++;
                        }
                        if (count > k){
                            list.add(false);
                        }else {
                            list.add(true);
                        }
                    }
                }
            }
        }
        return list;
    }

    // 进行一个回文判断
    public boolean isPlalindrome(char[] chars){
        int left = 0;
        int right = chars.length - 1;
        while (left <= right){
            if (chars[left] != chars[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public List<Boolean> canMakePaliQueries2(String s, int[][] queries) {
        int len = s.length();
        char[] sc = s.toCharArray();
        int tmp = 0;
        //统计每个字母的前缀数量
        int[][] dict = new int[26][len+1];
        for(int i = 1; i <= len; i++)
        {
            tmp = sc[i-1]-'a';
            for(int j = 0; j < 26; j++)
            {
                dict[j][i] = dict[j][i-1];// 前缀和预处理算法 就是说 算账营业额问题
            }
            dict[tmp][i]++;
        }

        List<Boolean> res = new ArrayList<>();
        for(int[] query : queries)
        {
            res.add(check(dict,sc, query[0], query[1], query[2]));
        }
        return res;
    }
    public boolean check(int[][] dict,char[] sc, int from, int to, int k)
    {
        //因为可以任意排序，可以将回文串的判断改为字母数量的统计判断
        //回文字符串中最多只能有一个字母的数量为奇数
        //设有m个字母的数量为奇数
        //当m为偶数，至少需要改动m/2个字母，将奇数的量降为0
        //当m为奇数，至少需要改动m/2个字母，将奇数的量降为1
        //因此比较m/2和k的大小就可以了
        int oddNum = 0;
        for(int i = 0; i < 26; i++)
        {
            if(((dict[i][to+1] - dict[i][from]) & 1)>0) oddNum++;
        }
        return (oddNum /2 <= k);
    }

    public static void main(String[] args) {
        String s = "abcda";
        int[][] qqueries = {
                {3,3,0},
                {1,2,0},
                {0,3,1},
                {0,3,2},
                {0,4,1}
        };
        for (Boolean aBoolean : new LeetCode1177().canMakePaliQueries2(s, qqueries)) {
            System.out.println(aBoolean);
        }
    }
}
